Implementing the Shell Sort Algorithm in C++

Shell Sort is an improved version of Insertion Sort, also known as "diminishing increment sort". It efficiently sorts arrays by performing insertion sorts on grouped subsequences and gradually reducing the increment. The basic idea is: select an initial increment `gap` (e.g., half the array length), group elements with intervals of `gap` (forming subsequences), perform insertion sort on each group; repeat by reducing `gap` (usually halving it) until `gap=1` to complete the overall sorting. Core principle: Larger `gap` reduces the number of moves by grouping, while smaller `gap` leaves the array partially sorted, significantly lowering the total number of moves in the final insertion sort. For instance, take the array `[12, 34, 54, 2, 3]` – after initial `gap=2` grouping and sorting, the array becomes more ordered, and then `gap=1` completes the final sort. The code implements Shell Sort with three nested loops: the outer loop controls the `gap`, the middle loop iterates through each group, and the inner loop shifts elements. The average time complexity is `O(n^1.3)` (dependent on the increment), with the worst-case `O(n²)`, and a space complexity of `O(1)`. It is unstable. By optimizing insertion sort through grouping, Shell Sort is suitable for larger arrays. Its core logic lies in "grouping → sorting → reducing increment → final sorting".